题解 AT1058@洛谷 | 1058@Atcoder 【とても長い文字列】

本题的数学方法有过了,我来一发循环链表(C/C++专属福利)。

根据题目意思,要我们循环遍历一个字符串。自然可以想到循环链表。

把样例1建入循环链表长什么样呢?如下图

可以看到效果很好。

关于循环链表的知识

代码:

#include <iostream>
using namespace std;

struct node
{
	char data;
	node* next;
};

int main()
{
	string s;
	int n;
	cin>>s>>n;
	int l = s.length();
	int k;
	node *first, *last;
	first = NULL, last = NULL;
	for(k=0;k<l;k++)
	{
		node *p = new node;
		p->data = s[k];
		p->next = NULL;
		if(k == 0) first = p;
		else
		{
			if(k == l - 1) p->next = first;
			last->next = p;
		}
		last = p;
	}
	last = first;
	for(k=1;k<n;k++,last=last->next);
	cout<<last->data<<endl;
	return 0;
}